



#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class MyCircularQueue
{
public:
    MyCircularQueue(int k)
        :_v(k + 1)
    {
        //_v.resize(k + 1);
    }

    bool enQueue(int value)
    {
        if (isFull())
            return false;

        _v[_end++] = value;
        _end = _end % _v.size();

        return true;
    }

    bool deQueue()
    {
        if (isEmpty())
            return false;

        _beg = (_beg + 1) % _v.size();

        return true;
    }

    int Front()
    {
        if (isEmpty())
            return -1;

        return _v[_beg];
    }

    int Rear()
    {
        if (isEmpty())
            return -1;

        return _v[(_end - 1 + _v.size()) % _v.size()];
    }

    bool isEmpty()
    {
        return _beg == _end;
    }

    bool isFull()
    {
        return _beg == (_end + 1) % _v.size();
    }
private:
    int _beg = 0;
    int _end = 0;
    vector<int> _v;
};

class MyCircularQueue1
{
public:
    MyCircularQueue1(int k)
        : _capacity(k)
    {}

    bool enQueue(int value)
    {
        if (_list.size() == _capacity)
            return false;

        _list.push_back(value);

        return true;
    }

    bool deQueue()
    {
        if (_list.empty())
            return false;

        _list.pop_front();

        return true;
    }

    int Front()
    {
        if (isEmpty())
            return -1;

        return _list.front();
    }

    int Rear()
    {
        if (isEmpty())
            return -1;

        return _list.back();
    }

    bool isEmpty()
    {
        return _list.empty();
    }

    bool isFull()
    {
        return _list.size() == _capacity;
    }
private:
    list<int> _list;
    size_t _capacity = 0;
};

class Solution
{
public:
    int firstMissingPositive1(vector<int>& nums)
    {
        int res = 0;
        unordered_set<int> hash(nums.begin(), nums.end());

        for (int i = 1, n = nums.size(); i <= n + 1; ++i)
        {
            if (!hash.count(i))
            {
                res = i;
                break;
            }
        }

        return res;
    }

    int firstMissingPositive2(vector<int>& nums)
    {
        int n = nums.size();

        for (int i = 0; i < n;)
        {
            if (nums[i] > 0 && nums[i] - 1 < n && nums[i] - 1 != i && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
            else
                ++i;
        }
        for (int i = 0; i < n; ++i)
        {
            if (nums[i] != i + 1)
                return i + 1;
        }

        return n + 1;
    }

    int tribonacci1(int n)
    {
        vector<int> dp(n + 1, 1);
        dp[0] = 0;

        for (int i = 3; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        return dp[n];
    }

    int tribonacci2(int n)
    {
        if (!n)
            return 0;
        if (n < 3)
            return 1;

        int res = 0;
        int a = 0, b = 1, c = 1;

        for (int i = 0; i < n - 2; ++i)
        {
            res = a + b + c;
            a = b;
            b = c;
            c = res;
        }

        return res;
    }

    int waysToStep1(int n)
    {
        if (n < 2)
            return 1;


        vector<int> dp(n + 1, 1);
        const int mod = 1000000007;

        dp[2] = 2;
        for (int i = 3; i <= n; ++i)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;
        }

        return dp[n];
    }

    int waysToStep2(int n)
    {
        if (n < 2)
            return 1;
        if (n < 3)
            return 2;

        int res = 0;
        int a = 1, b = 1, c = 2;
        const int mod = 1000000007;

        for (int i = 0; i < n - 2; ++i)
        {
            res = ((a + b) % mod + c) % mod;
            a = b;
            b = c;
            c = res;
        }

        return res;
    }

    int minCostClimbingStairs1(vector<int>& cost)
    {
        int n = cost.size();
        vector<int> dp(n + 1);

        for (int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }

        return dp[n];
    }

    int minCostClimbingStairs2(vector<int>& cost)
    {
        int n = cost.size();
        int cur = 0, pprev = 0, prev = 0;

        for (int i = 2; i <= n; ++i)
        {
            cur = min(pprev + cost[i - 2], prev + cost[i - 1]);
            pprev = prev;
            prev = cur;
        }

        return cur;
    }

    int numDecodings1(string s)
    {
        int n = s.size();
        vector<int> dp(n);

        dp[0] = s[0] == '0' ? 0 : 1;
        if (n < 2)
            return dp[0];

        if (s[1] >= '1' && s[1] <= '9')
            dp[1] = dp[0];
        int tmp = stoi(s.substr(0, 2));
        if (tmp >= 10 && tmp <= 26)
            ++dp[1];

        for (int i = 2; i < n; ++i)
        {
            if (s[i] >= '1' && s[i] <= '9')
                dp[i] = dp[i - 1];

            tmp = stoi(s.substr(i - 1, 2));
            if (tmp >= 10 && tmp <= 26)
                dp[i] += dp[i - 2];
        }

        return dp[n - 1];
    }

    int numDecodings2(string s)
    {
        int n = s.size();
        vector<int> dp(n + 1);

        dp[0] = 1;
        dp[1] = s[0] == '0' ? 0 : 1;

        for (int i = 2; i <= n; ++i)
        {
            if (s[i - 1] >= '1' && s[i - 1] <= '9')
                dp[i] = dp[i - 1];

            int tmp = stoi(s.substr(i - 2, 2));
            if (tmp >= 10 && tmp <= 26)
                dp[i] += dp[i - 2];
        }

        return dp[n];
    }

    int numDecodings3(string s)
    {
        int n = s.size();
        int prev = s[0] == '0' ? 0 : 1, pprev = 1, res = prev;

        for (int i = 2; i <= n; ++i)
        {
            res = 0;

            if (s[i - 1] != '0')
                res += prev;

            int tmp = stoi(s.substr(i - 2, 2));
            if (tmp >= 10 && tmp <= 26)
                res += pprev;

            pprev = prev;
            prev = res;
        }

        return res;
    }
};

void Test1()
{
    vector<int> nums({ 7, 8, 9, 11, 12 });

    cout << Solution().firstMissingPositive2(nums) << endl;
}

int main()
{
    Test1();

	return 0;
}